package com.example.demo.DS;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-06-08
 * Time: 14:51
 */
public class HashTable {
    //结点类
    public static class Entry {
        public Object key;//节点的key
        public Object val;//节点值
        public int hash;//哈希值
        public Entry next;//下一个节点

        public Entry(Object key, Object val, int hash) {
            this.key = key;
            this.val = val;
            this.hash = hash;
        }
    }
    //哈希表
    public Entry[] table;

    public HashTable() {
        //初始化长度为2的n次幂
        table = new Entry[16];
    }

    //数组有效长度
    public int size;

    //根据key获取到val
    public Object get(int hash,Object key) {
        //1.先根据hash值计算数组下标
        int idx = hash & (table.length- 1);
        Entry p = table[idx];
        //2.遍历链表进行查找key
        while(p!= null) {
            if(p.key .equals(key)) {
                return p.val;
            }
            p = p.next;
        }
        return null;
    }

    //放入key-val
    public void put(int hash,Object key,Object val) {
        //1.先根据hash值计算数组下标
        int idx = hash & (table.length- 1);
        Entry p = table[idx];
        //2.遍历链表进行查找key
        if(p == null) {
            table[idx] = new Entry(key, val, hash);
        }else {
            while (true) {
                if (p.key == key) {
                    //有重复的key,则覆盖掉
                    p.val = val;
                    return;
                }
                if (p.next == null) {
                    break;
                }
                p = p.next;
            }
            p.next = new Entry(key, val, hash);
        }
        size++;
    }
}